Masala #1027

Xotira 512 MB Vaqt 3000 ms Qiyinchiligi 30 %

#Dinamik dasturlash

#Ochko'z algoritm

#Tartiblash

#Prefix Sum

3.6 (Baholar 5)

Muallif: Обид Синдаров

Maksimal segmentlar yig'indisi

Qulmamat massivdagi so'rovlar haqidagi masalalarni juda yaxshi ko'radi.

Bir kun u juda mashhur masalaga duch keldi. $n$ ta elementli $a$ massiv beriladi va $q$ ta $l_i,r_i(1\leq l_i\leq r_i\leq n)$ so'rovlar mavjud. Har bir so'rovda massivning $l_i-$ elementidan $r_i-$ elementigacha bo'lgan barcha sonlarning yig'indisini hisoblash talab etiladi.

Bunday vazifa Qulmamatga juda zerikarli tuyildi. U surovlarga javob berishidan oldin massiv elementlarini aralashtirib, barcha so'rovlarga javoblar yig'indisi maksimal darajaga keltirishga qaror qildi. Sizning vazifangiz ushbu maksimal miqdorni hisoblashdan iborat.

Kiruvchi ma'lumotlar:

Birinchi satrda ikkita $n(1\leq n\leq 2000000)$ va $q(1\leq q\leq 2000000)$ butun sonlar. Kiyingi satrda $n$ ta $a_i(-10^9\leq a_i\leq 10^9)$ massiv elementlari beriladi va kiyingi $q$ satrda $l_i,r_i(1\leq l_i\leq r_i\leq n)$ so'rovlari beriladi.

Chiquvchi ma'lumotlar:

Yagona satrda masalani javobini $-$ massiv elementlari tartibini o'zgartirganingizdan so'ng so'rovlarga javoblarning maksimal yig'indisini chop eting.

Misollar

#	input.txt	output.txt
1	3 2 2 3 5 1 2 2 3	15

Izoh:

Birinchi testda [2, 3, 5] massivni [2, 5, 3] ko'rinishiga keltirsangiz so'rovlar $a_{[1..2]}=2+5=7$ va $a_{[2..3]}=5+3=8$ yig'indisi 15 ga teng.

Telegram Facebook

Yechimini yuborish

Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin